#include <iostream>
#include <vector>
using namespace std;

/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
 * 返回和为 target 的 nums 子序列中，子序列 长度的最大值 。
 * 如果不存在和为 target 的子序列，返回 -1 。
 * 子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
 * 
 * 示例 1：
 * 输入：nums = [1,2,3,4,5], target = 9
 * 输出：3
 * 解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。
 * 
 * 示例 2：
 * 输入：nums = [4,1,3,2,1,5], target = 7
 * 输出：4
 * 解释：总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。
 * 
 * 示例 3：
 * 输入：nums = [1,1,5,4,5], target = 3
 * 输出：-1
 * 解释：无法得到和为 3 的子序列。
 * 
 * 解题思路：动态规划，（背包问题）
 * 
 * 转移方程:dp[s] = max(dp[s], dp[s - num] + 1);
 * 表示容量为s的背包，所背的物品价值可以最大为dp[s]
 * 依赖关系(遍历关系):后面的状态依赖前面的状态，所以这里需要从后往前计算剩下的容量，
 * 防止将前面的修改了，影响后面的dp！
 * 
 */

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        vector<int> dp(target + 1, -1);
        dp[0] = 0;
        //在此题中背包所能够带的最大价值就是最长子序列的长度
        for(int num : nums) {
            //对于数组内所有的元素进行遍历
            for(int s = target; s >= num; s--) {
                if(dp[s - num] != -1) {
                    dp[s] = max(dp[s], dp[s - num] + 1);
                    // cout << "此题的检测过程（实际解题将以下的输出忽略）" << endl;
                    // cout << "s = " << s << "  " << dp[s] << endl;
                    // cout << "########################" << endl;
                }
            }
        }
        return dp[target] != -1 ? dp[target] : -1;
    }
};

